package com.liuzhilong.infrastructure.framework.algorithms.datastruct.line;

import java.lang.reflect.Array;

import static com.liuzhilong.infrastructure.framework.algorithms.datastruct.tree.TreeUtils.Arrays.*;

/**
 * <h1>优先级队列</h1>
 * <p>基于二叉堆实现的优先级队列,内部基于数组</p>
 * <p>可以根据大小自动扩容</p>
 * <p>JDK中也有实现{@link java.util.PriorityQueue}</p>
 * @param <T> 权重类型
 */
public class PriorityQueue<T extends Comparable<T>> {

    private T[] data;
    private int count=0;
    //是否是最小堆
    private boolean small=true;
    private Class<T> type;
    public PriorityQueue(Class<T> type, int size,boolean small) {
        if(size<=0){
            size = 1;
        }

        this.data = (T[]) Array.newInstance(type, size);
        this.type = type;
        this.small = small;
        this.count = 0;
    }

    public int size(){
        return count;

    }
    public boolean isEmpty(){
        return count == 0;
    }


    public void insert(T item){
        if(count == data.length){
            expansion();
        }
        //插入最后元素
        data[count]=item;
        shiftUp(count++);
    }
    //获取栈顶元素
    public T pull(){
        if(count<=0){
            return null;
        }
        T top = data[0];
        data[0] = null;
        swap(0,--count);
        shiftDown(0);
        if(count<=data.length/2&&data.length>200){
            compress();
        }
        return top;
    }


    /**
     * shiftup操作。
     * 与父节点比对，如果不符合规则 交换
     * @param i
     */
    private void shiftUp(int i ){
        if(i==0){//顶点不需要交换
            return;
        }
        if((small&&(less(i,parent(i))))
                ||(!small&&(than(i,parent(i))))){
            swap(i, parent(i));
            //查看父节点是否需要交换
            shiftUp(parent(i) );
        }
    }
    /**
     * 与子元素对比 如果不符合条件 下沉
     * @param i
     */
    private void shiftDown(int i){
        //查看是否越界
        if(left(i)>=count){
            return;
        }
        if(right(i)>=count){
            //右侧越界
            //只判断左侧

            //两个节点都是空的 不继续
            if(data[left(i)]==null){
                return;
            }
            if(small&&less(left(i),i)){
                //获取比较小的
                swap(i,left(i));
            }
            if(!small&&than(left(i),i)){
                //获取比较小的
                swap(i,left(i));
            }


            return;
        }

        //两个节点都是空的 不继续
        if(data[left(i)]==null&&data[right(i)]==null){
            return;
        }
        if(small&&(less(left(i),i)||less(right(i),i))){
            //获取比较小的
            int index = data[right(i)]==null||less(left(i),right(i))?left(i):right(i);
            swap(i,index);
            shiftDown(index);
        }
        if(!small&&(than(left(i),i)||than(right(i),i))){
            //获取比较小的
            int index = data[right(i)]==null||than(left(i),right(i))?left(i):right(i);
            swap(i,index);
            shiftDown(index);
        }
    }




    /**
     * 使用heapify方法，从最后一个非叶子节点开始，从下往上，对每个节点执行下沉(siftDown)操作，这样一开始就排除了一半的节点
     */
    private void heapify(){
        for(int i=parent(count-1);i>=0;i--){
            shiftDown(i);
        }
    }

    //最原始方法
    private void swap(int i, int j) {
        T id = data[i];
        data[i] = data[j];
        data[j] = id;
    }

    private void expansion(){

        T[] newData = (T[]) Array.newInstance(type, data.length*2);
        for (int i = 0; i < data.length; i++) {
            newData[i] = data[i];
            data[i] = null;
        }
        data = newData;
    }
    private void compress(){

        T[] newData = (T[]) Array.newInstance(type, (data.length-1)/2+1);
        for (int i = 0; i < newData.length; i++) {
            newData[i] = data[i];
            data[i] = null;

        }
        data = newData;
    }




    private boolean than(T t1,T t2){
        return t1.compareTo(t2) > 0;
    }
    private boolean less(T t1,T t2){
        return t1.compareTo(t2) < 0;
    }

    private boolean than(int t1,int t2){
        return than(data[t1],data[t2]);
    }
    private boolean less(int t1,int t2){
        return less(data[t1],data[t2]);
    }
}
